package com.tgy.algorithm._经典题目01;


/**
 *
 * 有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打
 * 包机上放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人
 * 将每个机器上的物品进行移动从而到达物品数量相等才能打包。
 * 每个物品重量太大 行移动，为了省力，只在相邻的机器上移动。
 * 请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。
 * 如果不能使每个机器上的物品相同，返回-1。
 *
 * 例如[1.0,5]表示有3个机器，每个机器上分别有1、0、5个物品，
 * 经过这些轮后:
 * 第一轮:1 <- 5 => 1 1 4
 * 第二轮:1 <- 1 <- 4 => 2 1 3
 * 第三轮:1 <- 3=> 2 2 2 移动了3轮，每个机器上的物品相等，所以返回3
 *
 * 例如[2,2,3]表示有3个机器，每个机器上分别有2、2、3个物品，
 * 这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1
 *
 */
public class _009_最小搬动次数 {

    //
    public static int minMove(int[] nums) {

        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }

        int len = nums.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }

        if (sum % len != 0) {
            return -1;
        }

        int avg = sum / len;
        int retMin = Integer.MIN_VALUE;
        int leftSum = 0;
        int rightSum;
        for (int i = 0; i < len; i++) {

           int leftWantValue = avg * (i - 1 + 1);
           int rightWantValue = avg * (len - i - 1);

           if (i - 1 >= 0) {
               leftSum += nums[i - 1];
           }

           rightSum = sum - leftSum - nums[i];

           int leftLeave = leftSum - leftWantValue;
           int rightLeave = rightSum - rightWantValue;

           if (leftLeave < 0 && rightLeave < 0) {
               retMin = Math.max(retMin,Math.abs(leftLeave) + Math.abs(rightLeave));
           }else {
               retMin = Math.max(Math.max(Math.abs(leftLeave),Math.abs(rightLeave)),retMin);
           }
        }

        return retMin;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,0,5};
        int count = minMove(nums);
        System.out.println(count);
    }
}
